def merge(A: list, B:list):
    """ Функция принимает на вход 2 массива - A и B.
        Возвращает новый массив С, отсортированный по возростанию.

    """

    i = k = n = 0

    C = [0] * (len(A) + len(B))

    while i < len(A) and k < len(B):
        if A[i] <= B[k]:
            C[n] = A[i]
            i += 1
            n += 1
        else:
            C[n] = B[k]
            k += 1
            n += 1
            
    while i < len(A):
        C[n] = A[i]
        i += 1
        n += 1
        
    while k < len(B):
        C[n] = B[k]
        k += 1
        n += 1

    return C


def merge_sort(A:list):
    """ Функция сортирует массив A методом слияния.
        Функция не создает новый массив, а изменяет входной.
        В ходе работы функция вызывает внешнюю функцию merge().

    """

    if len(A) <= 1:
        return

    middle = len(A)//2

    L = [A[i] for i in range(0, middle)]
    R = [A[i] for i in range(middle, len(A))]

    merge_sort(L)
    merge_sort(R)

    C = merge(L, R)

    for i in range(len(A)):
        A[i] = C[i]


def check_sort(A:list):
    """ Функция проверяет, отсортирован ли массив A.
        Возвращает True либо False.

    """

    for i in range(1, len(A)):
        if A[i] < A[i-1]:
            return False
        return True

def test_sort():

    a = [i for i in range(10, 20)] + [i for i in range(0, 10)] + [i for i in range(20, 30)]
    b = [0] * 10
    c = [i for i in range(10, -1, -1)]
    d = [i for i in range(6)]
    e = [5, 67, 13, 57, 53, 0, -3, -78]

    for (massiv, testNumber) in (a, 1), (b, 2), (c, 3), (d, 4), (e, 5):
        print(f'Test #{testNumber} ', end='')
        merge_sort(massiv)
        print('Ok') if check_sort(massiv) else print('Fail')

# test_sort()






